// 这个本来应该是算法的，也放到这里了
// 号称是最好的字符匹配算法

#include <stdio.h>
#include <string.h>

#define CHARSET_SIZE 256

#define max(a, b) (a) > (b) ? (a) : (b)

void badcharTable(const char* pattern, int* table)
{
    unsigned len = strlen(pattern);
    for (size_t i = 0; i < CHARSET_SIZE; i++)
    {
        table[i] = len;
    }

    for (size_t i = 0; i < len - 1; i++)
    {
        table[(int) pattern[i]] = len - 1 - i;
    }
    
}

int boyerMoore(const char* text, const char* pattern)
{
    int n = strlen(text);
    int m = strlen(pattern);
    int badChar[CHARSET_SIZE];
    badcharTable(pattern, badChar);

    int s = 0;
    while (s <= n - m)
    {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[s + j])
        {
            j --;
        }
        
        if (j < 0)
        {
            return s;
        } else
        {
            s += max(1, j - badChar[(int) text[s + j]]);
        }
        
    }
    return -1;
}

int main(void) {
    char text[] = "This is Bo a sample text for Boyer-Moore algorithm.";
    char pattern[] = "Boyer-Moore";

    int result = boyerMoore(text, pattern);
    if (result > -1)
    {
        printf("find the index is %d\n", result);
    } else
    {
        printf("not found\n");
    }
    return 0;
}